package tree.leetcode_94_medium;

import java.util.*;

public class InorderTraversal2 {
    public static void main(String[] args) {
        InorderTraversal2 i = new InorderTraversal2();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);
        System.out.println("中序遍历：");
        printList(i.inorderTraversal(root));

    }
    public static void printList(List<Integer> list){
        for (int i = 0; i<list.size(); i++){
            System.out.print(list.get(i)+" ");
        }
    }
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}
